Compression techniques are widely used in communication networks in order to reduce the size of data files and packets, and to thereby increase the amount of data that can be transmitted over a communication link with a particular bandwidth. Alternatively, the bandwidth that would otherwise be used to transmit the uncompressed data can be used to transmit other data.
There are many different types of compression techniques. In data transmission networks that use error corrected reliable channels, codebook or dictionary compression is often used. Examples of loss-less dictionary type of compression include the techniques known as Lempel-Ziv (LZ) coding and the technique known as Huffmann coding. Dictionary methods provide effective mechanisms for generic compression of data streams over a reliable channel. A reliable channel ensures no loss of data between a transmitter and a receiver. For example, in modem communication Lempel-Ziv based algorithms such as ITU (International Telecommunications Union) Recommendation V.44 and V.42 are often used over a reliable link layer. The reliable link is required to ensure that the compressor or encoder and the de-compressor or decoder remain in synchronization.
Another widely used simple type of compression can be termed “flag compression”, or “identical octet” compression. In this type of compression, a series of identical octets are replaced by transmitting information that identifies the octet and which indicates the length of the series. Thus, instead of transmitting a series of 25 flag octets a information would be transmitted indicating that there is a series of 25 flag octets. Herein this type of compression is termed “flag compression”; however, it should be understood that it can be applied to any series of identical octets.
The term “clear channel” as used herein means a loss-less communication channel which transmits a series of information bits over a packet network. The important point is that a clear-channel is a “bit oriented” communication channel. The packet network maybe lossy, but the user expects the output stream of bits to closely correspond to the input stream of bits. The transmitted bits can be a series of HDLC like packets, such as X.25, Frame relay, ISDN, SS7 etc, or the bits may have some other structure. Alternatively, a clear channel may merely provide a generic, constant bit rate, data pipe for an arbitrary application.
Dictionary based compression techniques such as Lempel-Ziv (LZ) coding or Huffmann coding can be used to increase the capacity of a clear channel. However, dictionary based techniques have certain deficiencies. (a) The compressor and de-compressor must be kept in synchronization. This means that loss of a packet means loss of synchronization between the compressor and the de-compressor. For subsequent data compression to occur, the compressor and the de-compressor must be synchronized and this can result in the loss of data in the interim period.
The present invention provides an efficient data compression technique for use with a clear channel which may be carrying a variety of different types of information, some of which can be compressed and some of which can not be compressed.